/*!
 * \file heurColoring.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Heuristics for coloring, maximum stable set and maximum clique.
 */

#include <stdlib.h>
#include <bitmap.h>
#include <graph.h>
#include <heurColoring.h>

static BitMap * BB; //!< Auxiliary bitmap used in various heuristics.
static BitMap * CC; //!< Auxiliary bitmap used in various heuristics.
static Graph * heurg; //!< Input graph of the heuristics.
static size_t memsz = 0; //!< Memory space used by the heuristics.

// mcsColoring
static int * nextInColor = NULL; //!< Vertices classified by colors

void initHeur(Graph * g) {
	heurg = g;
	BitMap * vec = newBitMapVector(2, g->n);
	BB = vec;
	CC = vec + 1;
//	memsz += (nnodes << LOGW);
	nextInColor = NULL;
}

void closeHeur() {
	freeBitMap(BB);
//	free(BB);
//	free(CC);
	BB = NULL;
	CC = NULL;
	heurg = NULL;

	if (nextInColor != NULL) {
		free(nextInColor);
		nextInColor = NULL;
	}
}

size_t getMemSize() {
	return memsz;
}

/*!
 * \fn int maxClique(BitMap * R)
 * \brief Greedy heuristic for maximum clique.
 *
 * The vertices in the specified bitmap are greedily searched for a maximum clique.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 *
 * \return The size of the clique found.
 */
int maxClique(BitMap * R) {
	int size = 0;
	Node nodeBB;

	printf("maxclique:");

	copyAll(BB, R);
	for (begin(BB, &nodeBB); !end(&nodeBB); next(&nodeBB)) {
		printf(" %d",getElement(&nodeBB));
		retainFrom(BB, neig(heurg, getElement(&nodeBB)), &nodeBB);
//		delElement(RR, &nodeidx);

		size++;
	}

	printf("\n");

	return size;
}

int greedyColoring(BitMap * B, int lim, int * R, int * C) {
	int size = 0;
	int i = 0;
	Node nodeCC;
	Node nodeBB;

	copyAll(CC, B);
	begin(CC, &nodeCC);
	beginWhile(BB, &nodeBB);
	while (!end(&nodeCC))
	{
		size++;
		copySets(&nodeBB, &nodeCC);
		do {
			int v = getElement(&nodeBB);
			if (size > lim) {
				R[i] = v;
				C[i++] = size - lim;
			}
			removeFrom(&nodeBB, neig(heurg, v));
//			delElement(BB, &nodeBB);
			delElement(CC, &nodeBB);
			next(&nodeBB);
		} while (!end(&nodeBB));

		next(&nodeCC);
	}

	return i;
}

static void mcsRecolor(BitMap * B, int size) {
	int sentinel = heurg->n << 1;

	Node node;
	int u = 0, v = 0, prevu, hasv;
	copyAll(BB, B);
	for (begin(BB, &node); (hasv = !end(&node)); next(&node)) {
		v = getElement(&node);
		int ucolor = 1;
		while (ucolor < size) {
			int curInColor = nextInColor[heurg->n + ucolor];
			int prevInColor = heurg->n + ucolor;
			int hasNeig = 0;
			while (hasNeig < 2 && curInColor < heurg->n) {
				if (hasEdge(heurg, v, curInColor)) {
					hasNeig++;
					u = curInColor;
					prevu = prevInColor;
				}
				prevInColor = curInColor;
				curInColor = nextInColor[curInColor];
			}

			if (hasNeig < 2) {
				int w = 0, wcolor = 0;
				if (hasNeig == 0) {
					w = v;
					wcolor = ucolor;
				} else {
					int cl = ucolor + 1;
					while (cl <= size) {
						int cc = nextInColor[heurg->n + cl];
						while (cc < sentinel && !hasEdge(heurg,u,cc))
							cc = nextInColor[cc];
						if (cc == sentinel) {
							w = u;
							wcolor = cl;
							nextInColor[prevu] = nextInColor[u];
							nextInColor[v] = nextInColor[heurg->n + ucolor];
							nextInColor[heurg->n + ucolor] = v;
							cl = size;
						}
						cl++;
					}
				}

				if (wcolor >= 1) {
					nextInColor[w] = nextInColor[heurg->n + wcolor];
					nextInColor[heurg->n + wcolor] = w;
//					delElement(RR, &node);
					ucolor = size;
					hasv = 0;
				}
			}
			ucolor++;
		}

		if (hasv)
			retainAll(BB, neig(heurg, v));
	}
}

static int partialColoring(BitMap * B, int lim) {
	int sentinel = heurg->n << 1;

	if (nextInColor == NULL) {
		nextInColor = (int *) calloc((heurg->n + 1) << 1, sizeof(int));
		memsz += (((heurg->n + 1) * sizeof(int)) << 1);
	}

	nextInColor[heurg->n] = sentinel;

	int size = 0;
	Node nodeCC;
	Node nodeBB;

	copyAll(CC, B);
	begin(CC, &nodeCC);
	beginWhile(BB, &nodeBB);
	while (size < lim && !end(&nodeCC)) {
		copySets(&nodeBB, &nodeCC);
//		printf("greedy-cor %d:",size);
//		printSetNodes(BB);
		do {
			int v = getElement(&nodeBB);
//			printf(" %d",v);
			removeFrom(&nodeBB, neig(heurg, v));
//			delElement(BB, &nodeBB);
			delElement(CC, &nodeBB);

			nextInColor[v] = nextInColor[heurg->n + size];
			nextInColor[heurg->n + size] = v;
			next(&nodeBB);
		} while (!end(&nodeBB));

		nextInColor[heurg->n + (++size)] = sentinel;
		next(&nodeCC);

//		printf("\n");
	}

	return size;
}

int mcsColoring(BitMap * B, int lim, int * R,	int * C) {
	if (lim <= 2 || lim < heurg->maxcq - (heurg->maxcq >> 2))
		return greedyColoring(B, lim, R, C);

	int i = partialColoring(B, lim);
	if (lim == i && isNotEmpty(B)) {
		mcsRecolor(CC, lim);
		return greedyColoring(CC, 0, R, C);
	}

	return 0;
}

int mcsColoring_f(BitMap * B, int lim, int * R,	int * C) {
	if (lim <= 1)
		return greedyColoring(B, lim, R, C);

	int i = partialColoring(B, lim);
	if (lim == i && isNotEmpty(B)) {
		mcsRecolor(CC, lim);
		return greedyColoring(CC, 0, R, C);
	}

	return 0;
}
